package violentRecursion;

import org.junit.Test;

/*
 *@description 最小路径和
 *@author hkfan
 *@version 1.0
 *@create 2025/5/16 16:42
 */
public class LeetCode_64 {


    @Test
    public void test(){
        int[][] grid = new int[][]{
                {1,3,1},
                {1,5,1},
                {4,2,1}
        };
        System.out.println(minPathSum(grid));

    }

    int res=Integer.MAX_VALUE;

    public int minPathSum(int[][] grid) {
        res=Integer.MAX_VALUE;
        solution_2(grid,0,0,grid[0][0]);
        return res;
    }

    /**
     * @description 暴力递归
     * @author hkfan
     * @throws
     * @time 2025/5/16 16:59
     */
    private void solution_1(int[][] grid, int x, int y, int score) {
        //1. 条件判断
        if (x==grid.length-1 && y==grid[0].length-1){
            res = Math.min(res,score);
        }
        //2. 递归循环
        if (x<grid.length-1){
            solution_1(grid,x+1,y,score+grid[x+1][y]);
        }
        if (y<grid[0].length-1){
            solution_1(grid,x,y+1,score+grid[x][y+1]);
        }
    }


    /**
     * @description 动态规划
     * @author hkfan
     * @throws
     * @time 2025/5/16 16:59
     */
    private void solution_2(int[][] grid, int x, int y, int score) {
        //1. 定义变量
        int[][] dp = new int[grid.length][grid[0].length];
        //2. 设置初值
        dp[grid.length-1][grid[0].length-1]=grid[grid.length-1][grid[0].length-1];
        for (int j = grid[0].length-2; j >=0 ; j--) {
            dp[grid.length-1][j]=grid[grid.length-1][j]+dp[grid.length-1][j+1];
        }
        for (int i = grid.length-2; i >=0 ; i--) {
            dp[i][grid[0].length-1]=grid[i][grid[0].length-1]+dp[i+1][grid[0].length-1];
        }
        //3. 填充dp数组
        for (int i = grid.length-2; i >=0 ; i--) {
            for (int j = grid[0].length-2; j >=0 ; j--) {
                dp[i][j]=grid[i][j]+Math.min(dp[i+1][j],dp[i][j+1]);
            }
        }
        res = dp[0][0];

    }

}
